package com.yaoli.niuke;

import com.yaoli.ajob.TreeNode;

import java.util.ArrayList;

/**
 * Created by will on 2017/5/9.
 */
public class _010_Test {
    public static void main(String[] args) {
        TreeNode  a = new TreeNode(10);
        TreeNode  b = new TreeNode(5);
        TreeNode  c = new TreeNode(12);

        TreeNode  d = new TreeNode(4);
        TreeNode  e = new TreeNode(7);




        a.setLeft(b);
        a.setRight(c);

        b.setLeft(d);
        b.setRight(e);


        _010_Test test = new _010_Test();
        test.FindPath(a,22);
    }

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        if(root == null){
            return result;
        }

        calc(root,target,0);

        return result;
    }

    //   10
    //  5  12
    // 4  7
    public void calc(TreeNode node , int target , int sum){
        if(node != null){

            help(node, target, 0 , new ArrayList<Integer>());

            calc(node.left,target,0);

            calc(node.right,target,0);
        }
    }

    public void help(TreeNode node, int target ,int sum ,ArrayList<Integer> list){
        if(node != null){
            list.add(node.val);
            if(node.left == null && node.right == null && node.val + sum == target){
                // (ArrayList<Integer>)list.clone();
                result.add((ArrayList<Integer>)list.clone());
            }

            help(node.left, target, node.val + sum,list);

            help(node.right, target, node.val + sum,list);

            list.remove(list.size() - 1);
        }
    }
}
